#include<bits/stdc++.h>
using namespace std;
int n,a[1000000];
int T,ans;
int q[1000000];
void dfs(int step){
    if(step>n){
            int cnt=0;
        for(int i=1;i<=n;i++){
            int j=i;
            while(1){
                if(a[j]==a[i]&&q[i]==q[j]||j==0)break;
                j--;
            }
            cnt+=a[j];
        }
        ans=max(ans,cnt);
    }else{
       for(int i=step;i<=n;i++){
            q[step]=1;
            dfs(step+1);
            q[step]=2;
            dfs(step+1);
       }
    }
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin>>T;
    for(int i=1;i<=T;i++){
            memset(q,0,sizeof(q));
            ans=0;
            cin>>n;
            for(int j=1;j<=n;j++)
                cin>>a[j];
            dfs(1);
            cout<<ans<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
